#include <iostream>
#include <vector>
#include <string>

using namespace std;

int count = 0;

bool IsSafe(int now[]) {
	if ((now[1] == now[2]) && (now[0] != now[1]))
		return false;
	if ((now[2] == now[3]) && (now[0] != now[2]))
		return false;
	return true;
}

bool isRepeated(int now[], const vector<int>& dira, int a, int step) {
	for (int i = 0; i < step; i++) {
		if (dira[i] == a) {
			return true;
		}
	}
	return false;
}

void display(const vector<int>& dira) {
	for (int i = 0; i <= 17; i++) {
		cout <<dira[i];
	}
	cout << endl;
}

void path(const vector<int>& dira) {
	int i = 0;
	while (dira[i] != 0) {
		switch (dira[i] - dira[i + 1]) {
		case 8:
		case -8:
			cout << "农夫独自过河\n";
			break;
		case 12:
		case -12:
			cout << "农夫带狼过河\n";
			break;
		case 10:
		case -10:
			cout << "农夫带羊过河\n";
			break;
		case 9:
		case -9:
			cout << "农夫带菜过河\n";
			break;
		default:
			cout << "未知动作\n";
			break;
		}
		i++;
	}
}

void backtracking(int now[], vector<int>& dira, int step) {
	int a = now[0] * 8 + now[1] * 4 + now[2] * 2 + now[3] * 1;
	
	if (isRepeated(now, dira, a, step) || !IsSafe(now)) {
		return;
	}
	dira[step] = a;
	
	if (now[0] == 0 && now[1] == 0 && now[2] == 0 && now[3] == 0) {
		count++;
		cout << "过河的第" << count << "的方法\n";
		path(dira);
		cout << endl;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (now[i] == now[0]) { 
			int temp[4];
			for (int j = 0; j < 4; j++) {
				temp[j] = now[j];
			}
			
			now[i] = !now[i];
			if (i != 0) {
				now[0] = !now[0];
			}
			backtracking(now, dira, step + 1);
			for (int j = 0; j < 4; j++) {
				now[j] = temp[j];
			}
		}
	}
}

int main() {
	int now[4] = {1, 1, 1, 1};
	vector<int> dira(18, 0);
	backtracking(now, dira, 0);
	return 0;
}
